package leetcode_800;

/**
 *@author 周杨
 *PreimageSizeOfFactorialZeroesFunction_793 判断有多少个数的阶乘后导0是k
 *describe:找规律 只有5的出现会使 0增加 再用二分查找优化 AC 66%
 *2018年10月23日 上午9:45:54
 */
public class PreimageSizeOfFactorialZeroesFunction_793 {
	public int preimageSizeFZF(int K) {
        long left = 0, right = 5L * (K + 1);
        while (left < right) {
            long mid = left + (right - left) / 2, cnt = 0;
            for (long i = 5; mid / i > 0; i *= 5) {
                cnt += mid / i;
            }
            if (cnt == K) return 5;
            else if (cnt < K) left = mid + 1;
            else right = mid;
        }
        return 0;
    }
}
